Distanz (Graphentheorie)

Dieser Text beschreibt Distanz (Graphentheorie).

Als Distanz oder Abstand zweier Knoten in einem Graph bezeichnet man die LĂ€nge eines kĂŒrzesten Pfades zwischen diesen. Falls ein solcher Pfad nicht existiert, so setzt man den Abstand auf unendlich. Der Abstand eines Knoten zu sich selbst ist Null.

Man beachte, dass in gerichteten Graphen der Abstand von der Richtung des Pfades abhÀngt. Dabei kann es sogar vorkommen, dass ein endlicher Abstand ca. in eine Richtung existiert.

Die Ermittlung des kĂŒrzesten Abstands zweier Knoten ist zu dem Beispiel fĂŒr Routenplaner wichtig. Er lĂ€sst sich auf einfache Weise mit dem Algorithmus von Dijkstra berechnen.

Aus den paarweisen Distanzen aller Knoten eines Graphen lÀsst sich der Distanzgraph konstruieren.== Beispiele ==

Ein Beispiel fĂŒr den Abstand in Graphen ist der Abstand zweier Personen in Sozialen Netzwerken. Dabei werden die Personen als Knoten reprĂ€sentiert, zwischen denen jeweils eine Kante existiert wenn sie einander kennen oder durch eine anderes Merkmal miteinander verbunden sind (siehe dazu auch das Small World PhĂ€nomen und die Erdös-Zahl).